package sort.test3_30;

public class HeapSort {

    public  int[] heapSort(int[] nums){
        if (nums.length==0){
            return null;
        }
        for (int i = nums.length/2-1; i >=0 ; i--) {
            adjustHeap(nums,i, nums.length);
        }
        //todo:这一块理解有误　
//        int curlength = nums.length;
//        for (int j = 0; j < curlength; j++) {
//            int temp=nums[0];
//            nums[0]=nums[curlength-1];
//            nums[curlength-1]=temp;
//            adjustHeap(nums,0,curlength--);
//        }

        //  CKG TODO 2023/3/31:  刚好调整完之后　调整堆的长度又减少了１
        for(int j=nums.length-1;j>0;j--){
            //交换
           int  temp=nums[j];
            nums[j]=nums[0];
            nums[0]=temp;
            adjustHeap(nums,0,j);
        }
        return  nums;
    }

    public void adjustHeap(int[] nums,int i,int length){
        int temp=nums[i];
        for (int k = 2*i+1; k <length ; k=2*k+1) {
            if (k+1<length&&nums[k]<nums[k+1]){
                k++;
            }
            if (nums[k]>temp){
                nums[i]=nums[k];
                i=k;
            }
            else {
                break;
            }
        }
        nums[i]=temp;
    }

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] a={1,5,3,9,4,7};
        int[] ints = heapSort.heapSort(a);
        for (int b: ints
             ) {
            System.out.println(b);

        }
    }










}
